package leecode.q402;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    Deque<Character> stack = new LinkedList<>();

    public String removeKdigits(String num, int k) {
        int length = num.length();
        if (length == 0 || length == k) {
            return "0";
        }
        for (int i = 0; i < length; i++) {
            char cur = num.charAt(i);
            if (!stack.isEmpty() && cur < stack.peekFirst() && k > 0) {
                while (!stack.isEmpty() && cur < stack.peekFirst() && k > 0) {
                    stack.removeLast();
                    k--;
                }
                if (stack.isEmpty()) {
                    if (cur != '0') {
                        stack.offerLast(cur);
                    }
                } else {
                    stack.offerLast(cur);
                }
            } else {
                if (stack.isEmpty()) {
                    if (cur != '0') {
                        stack.offerLast(cur);
                    }
                } else {
                    stack.offerLast(cur);
                }
            }


        }
        for (int i = 0; i < k; i++) {
            if (!stack.isEmpty()) {
                stack.removeLast();
            }
        }
        if (stack.size() == 0) return "0";

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pollFirst());
        }
        return sb.toString();
    }
}
